package wh.环形链表;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/4/6 21:24
 * @description:给你一个链表的头节点 head ，判断链表中是否有环
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(4);
        ListNode head = new ListNode();//头节点
        ListNode last = new ListNode();//尾指针
        head.next = node1;
        node1.next = node2;
        last = node2;
        last.next = head;
       // ListNode head = new ListNode(3);
        boolean b = hasCycle(head);
        System.out.println(b);
    }

    //解法1使用哈希set来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。
    public static boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        //set集合不存储重复的元素
        Set<ListNode> set = new HashSet<>();
        while (head != null){
            //程序走到这里时候，是先执行了add方法，然后对其返回结果进行判断，所以不管结果如何，都会执行add方法
            if(!set.add(head)){
                return true;
            }
            head = head.next;
        }
        return false;
    }

    //解法2快慢指针
    public static boolean hasCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        //初始设置时，让fast在slow的前面是为了保证while的执行
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast){
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

}
